﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Algorithm.Struct
{
    /// <summary>
    /// 二叉查找树满足一下一些条件：
    /// 如果x 是某个节点，y是它的左节点，则 value(y)<=value(x),如果y是它的右孩子则value(x)<value(y)
    /// </summary>
    public class SearchBTree<T> : BTree<T> where T : IComparable<T>, IEquatable<T>
    {

        public SearchBTree(TreeNode<T> root)
            : base(root)
        { }

        public TreeNode<T>[] Sort()
        {
            return Root.BTreeSort().ToArray();
        }
    }

    public static class TreeNodeExtend
    {
        public static List<TreeNode<T>> BTreeSort<T>(this TreeNode<T> node) where T : IComparable<T>
        {
            List<TreeNode<T>> result = new List<TreeNode<T>>();
            if (null != node)
            {
                var left = node.LeftNode.BTreeSort<T>();
                result.AddRange(left);
                result.Add(node);
                var right = node.RightNode.BTreeSort<T>();
                result.AddRange(right);
            }
            return result;
        }

        public static TreeNode<T> BTreeSearch1<T>(this TreeNode<T> node, T x)where T : IComparable<T>,IEquatable<T>
        {
            if (null == node || node.Data.Equals(x))
            {
                return node;
            }
            if (x.CompareTo(node.Data) < 0)
            {
                return node.LeftNode.BTreeSearch1<T>(x);
            }
            else
            {
                return node.RightNode.BTreeSearch1<T>(x);
            }
        }

        public static TreeNode<T> BTreeSearch2<T>(this TreeNode<T> node, T x) where T : IComparable<T>, IEquatable<T>
        {
            var tmpNode = node;
            while (null != tmpNode && !tmpNode.Data.Equals(x))
            {
                if (x.CompareTo(node.Data) < 0)
                {
                    tmpNode = tmpNode.LeftNode;
                }
                else
                {
                    tmpNode = tmpNode.RightNode;
                }
            }
            return tmpNode;
        }

        public static TreeNode<T> MinNode<T>(this TreeNode<T> node) where T : IComparable<T>
        {
            var tmp = node;
            while (null != tmp.LeftNode)
            {
                tmp = tmp.LeftNode;
            }
            return tmp;
        }

        public static TreeNode<T> MaxNode<T>(this TreeNode<T> node) where T : IComparable<T>
        {
            var tmp = node;
            while (null != tmp.RightNode)
            {
                tmp = tmp.RightNode;
            }
            return tmp;
        }

        /// <summary>
        /// 寻找前驱，前驱定义：比当前node 中的值大的节点中的最小值
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="node"></param>
        /// <returns></returns>
        public static TreeNode<T> GetSuccessor<T>(this TreeNode<T> node) where T : IComparable<T>
        {
            if (null != node.RightNode)
            {
                return node.RightNode.MinNode<T>();
            }
            var parent = node.Parent;
            var tmp = node;
            while (null != parent && node == parent.RightNode)
            {
                tmp = parent;
                parent = parent.Parent;
            }

            return parent;
        }

        /// <summary>
        /// 二叉查找树 插入说明：首先从根节点开始按照查找的顺序找到某个叶子节点，因为是按照查找顺序找到的叶子节点所以如果把
        /// 该节点放入这个叶子节点下的话，该二叉查找树还满足性质，如果小于该叶子节点就放到左树，大于等于就放到右树。
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="root"></param>
        /// <param name="node"></param>
        public static void Insert<T>(this TreeNode<T> root, TreeNode<T> node,SearchBTree<T> tree) where T : IComparable<T>, IEquatable<T>
        {
            node.Tree = tree;
            TreeNode<T> nodeParent = null;
            var tmp = root;
            while (null != tmp)
            {
                nodeParent = tmp;
                if (node.Data.CompareTo(tmp.Data) < 0)
                {
                    tmp = tmp.LeftNode;
                }
                else
                {
                    tmp = tmp.RightNode;
                }
            }
            node.Parent = nodeParent;
            if (null == nodeParent)
            {
                tree.Root = node;
            }
            else if (node.Data.CompareTo(nodeParent.Data) < 0)
            {
                nodeParent.LeftNode = node;
            }
            else
            {
                nodeParent.RightNode = node;
            }
        }

        /// <summary>
        /// 分三种情况讨论：1、该节点没有子节点，直接删除，让父节点指向为空，该节点的父指针为空
        ///                 2、该节点有一个节点，直接连接该节点的子节点与该节点的父节点
        ///                 3、如果有两个子节点，首先找到该及节点的后继，把该后继节点先删除(后继节点一定为左节点)
        ///                    然后把后继节点的内容复制到该节点中。
        /// 下面的算法在写法上对上面的三种情况进行了优化，请注意。。。。
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="root"></param>
        /// <param name="node"></param>
        public static TreeNode<T> Delete<T>(this TreeNode<T> root, TreeNode<T> node) where T : IComparable<T>, IEquatable<T>
        {
            TreeNode<T> willDel = null;
            if (null == node.LeftNode || null == node.RightNode)
            {
                willDel = node;
            }
            else
            {
                willDel = node.GetSuccessor();
            }

            TreeNode<T> willDelChild = null;
            if (null != willDel.LeftNode)
            {
                willDelChild = willDel.LeftNode;
            }
            else
            {
                willDelChild = willDel.RightNode;
            }

            //更新原孙子节点父指针指向
            if (null != willDelChild)
            {
                willDelChild.Parent = willDel.Parent;
            }

            //如果被删除的是根节点
            if (null == willDel.Parent)
            {
                root = willDelChild;
            }
            else if (willDel == willDel.Parent.LeftNode) //更新原祖父节点的孩子指针
            {
                willDel.Parent.LeftNode = willDelChild;
            }
            else
            {
                willDel.Parent.RightNode = willDelChild;//更新原祖父节点的孩子指针
            }

            //下面的判断说明willDel 节点为后继节点
            if (willDel != node)
            {
                node.Data = willDel.Data;
            }

            return willDel;
        }
    }
}
